﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0098_IntegerBreak : IAlgorithm
    {
        // 343. 整数拆分

        // 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

        // 说明: 你可以假设 n 不小于 2 且不大于 58。

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            Console.WriteLine(IntegerBreak(8));
        }

        // 算法
        public int IntegerBreak(int n)
        {
            if (n < 4)
                return n - 1;
            int[] dp = new int[n + 1];
            dp[2] = 1;
            for (int i = 3; i <= n; i++)
                dp[i] = Math.Max(Math.Max(2 * (i - 2), 2 * dp[i - 2]), Math.Max(3 * (i - 3), 3 * dp[i - 3]));
            return dp[n];
        }
    }
}
